package Stack;

import java.util.Stack;

public class _331_VerifyPreorderSerializationofaBinaryTree {
    public boolean isValidSerialization(String preorder) {
        if(preorder==null || preorder.equals("")) return false;
        if(preorder.equals("#")) return true;
        String[] vals  = preorder.split(",");
        Stack<String> stack = new Stack();
        if(vals.length%2==0) return false;
        for (int i = 0; i < vals.length; i++) {
            String val = vals[i];
            while (val.equals("#") && !stack.isEmpty() && stack.peek().equals(val)) {
                stack.pop();
                if (stack.isEmpty() || stack.peek().equals("#")) {
                    return false;
                }
                stack.pop();
            }
            stack.push(val);
        }
        return stack.size() == 1 && stack.peek().equals("#");
    }
}
